/**
 * @file Stack.c
 * @author Monomania(13015159350@qq.com)
 * @brief 利用堆栈解决四则运算问题【后缀表达法】
 * 
 * @version 0.1
 * @date 2021-08-30
 * @copyright Copyright (c) 2021
 * 
 */

/**后缀表达式规则说明
 * 公式（中缀表达式）：9 + (3-1)*3 + 10/2    --- 这个为中缀表达式
 * 
 * 中缀表达转后缀表达式规则：（栈用来存符号）
 *      从左到右遍历，遇到数字就输出成为后缀表达式的一部分；
 *      遇到符号，则判断其与栈顶符号的优先级，若符号的优先级低于栈顶符号（先乘除后加减）【假如是右括号，则直接全部输出到左括号为止】，--- 左括号的优先级很低，比符号低
 *      则栈顶元素依次出栈并输出到左括号为止（括号就不要输出了，直接丢弃），并把当前符号进栈，直到最终输出后缀表示为止。
 * 实例：遇到9--->输出;
 *       遇到 + 入栈;【此时栈内元素：+】
 *       遇到（ 入栈;此时栈内元素：+（】
 *       遇到3--->输出;
 *       遇到 - 入栈;【此时栈内元素：+（-】----左括号的优先级很低，比符号低
 *       遇到1--->输出;
 *       遇到）---出栈到（为止--->输出-;【此时栈内元素：+】
 *       遇到* 入栈;【此时栈内元素：+*】----优先级高的入栈
 *       遇到3--->输出;
 *       遇到+--->出栈-->输出 * +，并把+入栈;【此时栈内元素+】---由于没有遇到（所以全部出栈。
 *       遇到10--->输出;
 *       遇到/入栈;
 *       遇到2--->输出;
 *       没了--检查栈是否为空---不空则全部输出
 * 
 * 
 * 后缀表达式：9 3 1 - 3 * + 10 2 / +
 * 
 * 后缀表达式计算方式规则：（栈用来存数字）
 *      从左到右依序遍历，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈进行运算。
 *      运算结果再进栈，直到获得最终结果。
 * 
 */

#include <windows.h>
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
// #define NDEBUG
#include "assert.h"

// #include <conio.h> //清除命令行


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
// 定义一个不可能的数
#define INF   -99999  


typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


/****************************************************************/
/* 链栈结构 */
typedef struct StackNode
{
        SElemType data;
        struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct
{
        LinkStackPtr top;   // 指针，用于指向链表的节点
        int count;
}LinkStack;
/****************************************************************/


Status visit(SElemType c)
{
        printf("%d ",c);
        return OK;
}

/**
 * @brief 初始化堆栈
 * 
 * @param S 
 * @return Status 
 */
Status InitStack(LinkStack *S)
{
    S->count = 0;
    S->top = NULL;
    return OK;
}


/**
 * @brief 若栈为空，返回true，否则返回false。
 * 
 * @param S 
 * @return Status 
 */
Status StackEmpty(LinkStack S)
{
    if (S.top == NULL)
        return TRUE;
    return FALSE;
}


/**
 * @brief 将栈清空。
 * 
 * @param S 
 * @return Status 
 */
Status ClearStack(LinkStack *S)
{
    LinkStackPtr tmp_s;
    if (S->top != NULL) // 没空
    {
        tmp_s = S->top;
        S->top = S->top->next;
        free(tmp_s);
    }
    S->count = 0;
    return OK;
}

/**
 * @brief Get the Top object
 * 
 * @param S 
 * @return Status 
 */
SElemType GetTop(LinkStack S)
{
	SElemType tmp;
	if (S.top != NULL)
    {
        tmp = S.top->data;
        return tmp;
    }
    return ERROR;
}

/**
 * @brief 若栈S存在，插入新元素e到栈S中并成为栈顶元素
 * 
 * @param S 
 * @param e 
 * @return Status 
 */
Status Push(LinkStack *S, SElemType e)
{
    LinkStackPtr new_s = (LinkStackPtr)malloc(sizeof(StackNode));
    assert(new_s != NULL);
    if (new_s == NULL)  //内存分配失败
        return ERROR;  
    new_s->data = e;
    new_s->next = S->top;  /* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
    S->top = new_s;   /* 将新的结点s赋值给栈顶指针，见图中② */
    S->count++;
    return OK;
}


/**
 * @brief 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
 * 
 * @param S 
 * @return Status 
 */
SElemType Pop(LinkStack *S)
{
	SElemType tmp = 0;
	LinkStackPtr p;
	if(StackEmpty(*S))
			return ERROR;
	tmp=S->top->data;
	p=S->top;					/* 将栈顶结点赋值给p，见图中③ */
	S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
	free(p);                    /* 释放结点p */        
	S->count--;
	return tmp;
}


/**
 * @brief 返回S的元素个数，即栈的长度
 * 
 * @param S 
 * @return int 
 */
int StackLength(LinkStack S)
{ 
        return S.count;
}


Status StackTraverse(LinkStack S)
{
        LinkStackPtr p;
        p=S.top;
        while(p)
        {
                 visit(p->data);
                 p=p->next;
        }
        printf("\n");
        return OK;
}

void showMenu(const char* tips)
{
    printf("================================================================\n");
    printf("\t\t\t %s \t\t\t\t\n", tips);
    printf("----------------------------------------------------------------\n");
    return;
}

/**
 * @brief 判断优先级
 * 
 * @param c 
 * @return int 
 */
int Priority(char c)
{
	switch(c)
	{
		case '(':
			return 3;
		case '*':
		case '/':
			return 2;
		case '+':
		case '-':
			return 1;
		default:
			return 0;
	}
}
 

double Calculate(char* str)
{
	LinkStack S_num;   // 数字
    LinkStack S_opt; // 符号
	int i = 0, tmp = 0, j = 0;
	// 初始化
	if(InitStack(&S_num) != OK || InitStack(&S_opt) != OK)
	{
		printf("Init Failure!\n");
		exit(1);
	}
	while(str[i] != '\0' || !StackEmpty(S_opt))
	{
		//处理空格
		if (str[i] == ' ')
        {
            i++;
            continue;
        }
		//当为数字时
		if(str[i] >= '0' && str[i] <= '9')
		{
			for (; str[i] >= '0' && str[i] <= '9';i++)
				tmp = tmp * 10 + str[i] - '0';
			//这里已经不是数字了
			// tmp = tmp * 100; //处理浮点数
			Push(&S_num,tmp);
			tmp = 0;
		}
		else
		{
			// 非数字
			if((StackEmpty(S_opt) == OK) || (GetTop(S_opt) == '(' && str[i] != ')') || Priority(str[i]) > Priority(GetTop(S_opt)))//进栈不参与运算
			{
				Push(&S_opt,str[i]);
				i++;
				continue;
			}

			if(GetTop(S_opt) == '(' && str[i] == ')')//出栈不参与运算
			{
				Pop(&S_opt);
				i++;
				continue;
			}
			if((str[i] == '\0' && StackEmpty(S_opt) != OK) || (str[i] == ')' && GetTop(S_opt) != '(') || Priority(str[i]) <= Priority(GetTop(S_opt)))//出栈并参与运算
			{
				switch(Pop(&S_opt))
				{
					case '+':
						Push(&S_num, Pop(&S_num) + Pop(&S_num));
						break;
					case '-':
						j = Pop(&S_num);
						Push(&S_num, Pop(&S_num) - j);
						break;
					case '*':
						Push(&S_num, Pop(&S_num) * Pop(&S_num));
						break;
					case '/':
						j = Pop(&S_num);
						Push(&S_num, Pop(&S_num) / j);
				}
				continue;
			}
		}
	}

	return Pop(&S_num);
}


int main(int argc, char* argv[])
{
	double result = INF;
	char str[100]={0};

	system("cls");//清除命令行
	// clrscr();//清除命令行
	Sleep(500);
	
 /***************************************************************/
    showMenu("欢迎使用：");

	printf("请输入运算公式（回车结束）: ");
    // scanf("%s",str);   //遇到空格就停了
    gets(str);
    // printf("%s\r\n", str);

    // for (i = 0;str[i] != '\0'; i++)
    // {
    //     if (str[i] == ' ')
    //         printf("有空格");
    // }
    // i = 0;

	result = Calculate(str);
	if (result != INF)
		printf("计算结果：%d\r\n", result);
	else
		printf("计算结果：INF\r\n");
	return 0;
}


